// #include<vector>
// #include<limits>
// #include<cstddef>
// #include<iostream>
// #include<sstream>
// #include<map>
// #include<algorithm>
// #include<tuple>
// #include<unordered_map>
// #include<functional>
// #include<memory>
// using namespace std;
// typedef std::tuple<int,int> keyT;
// struct key_hash : public std::unary_function<keyT, std::size_t>{
//     std::size_t operator()(const keyT& k) const {
//         return std::get<0>(k) ^ std::get<1>(k);
//     }
// };
// struct key_equal : public std::binary_function<keyT, keyT, bool>{
//     bool operator()(const keyT& v0, const keyT& v1) const{
//         return std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1);
//     }
// };
// typedef std::unordered_map<const keyT, int, key_hash, key_equal > map_t;
// // typedef std::unordered_map<const keyT, keyT, key_hash, key_equal > state_t;

// class Chair{
// public:
//     map_t cache;
//     // map_t nextState;
//     vector<int> *arr;
//     vector<int> sum;
//     void InitSum(){
//         auto sumV = 0;
//         for(auto i = 0; i < arr->size(); i++){
//             sum.push_back(sumV);
//             sumV += (*arr)[i];
//         }
//         sum.push_back(sumV);
//     }
//     //合并区间 最后乘积
//     int MinMul(int s, int e){
//         if(s >= e) return 0;
//         if(s == e) return 0;//(*arr)[s];
//         auto key = std::make_tuple(s, e);
//         if(cache.find(key) != cache.end()) cache[key];
//         //划分区间
//         auto minMulV = std::numeric_limits<int>::max();
//         for(auto i = s; i < e; i++){
//             auto m1 = MinMul(s, i);
//             auto m2 = MinMul(i+1, e);
//             //子数组消耗 + 自身消耗
//             auto sv = m1+m2 + (sum[e+1]-sum[i+1])*(sum[i+1]-sum[s]);
//             // m1 *= m2;
//             // if(sv < minMulV) {
//             minMulV = min(sv, minMulV);
//                 // nextState[key] = i;
//             // }
//         }
//         cache[key] = minMulV;
//         return minMulV;
//     }

// };

// int main(int, char**) {
//     // vector<int> dt{
//     //     // 1, 2,
//     //     5, 1, 2,
//     // };
//     string n;
//     while(true) {
//         if(!getline(cin, n)) break;
//         if(n.size() == 0) break;
//         auto nn = stoi(n);

//         string data;
//         getline(cin, data);
//         std::stringstream iss(data);
//         std::vector<int> allTok;
//         std::string token;
//         while(std::getline(iss, token, ' ')){
//             if(token.size() > 0) {
//                 allTok.push_back(std::stoi(token));
//             }else {
//                 break;
//             }
//         } 

//         // vector<int> dt;
//         Chair ch;
//         ch.arr = &allTok;
//         ch.InitSum();
//         auto ms = ch.MinMul(0, allTok.size()-1);

//         // auto sum = 0;
//         // auto init = std::make_tuple(0, dt.size()-1);
//         // while(ch.cache.find(init) != ch.cache.end()){
//         //     sum += ch.cache[init];
//         //     if(ch.nextState.find(init) != ch.nextState.end()){

//         //     }
//         // }
//         cout << ms << endl;
//     }

// }